"""
题目：在双链表的第 n个位置插入新节点，位置无效则返回原链表。
"""


class Node:
    def __init__(self, val=0, prev=None, next=None):
        self.val = val
        self.prev = prev
        self.next = next


"""在双链表第pos个位置（1开始）插入节点"""
def insert_at_position(head, pos, val):
    if pos < 1:
        return head  # 位置无效
    # 插入头部（pos=1）
    if pos == 1:
        new_node = Node(val)
        if head:
            new_node.next = head
            head.prev = new_node
        return new_node
    # 查找插入位置的前驱节点（第pos-1个节点）
    current = head
    for _ in range(pos - 2):  # 循环pos-2次到达pos-1位置
        if current is None:
            return head  # 位置超出范围
        current = current.next
    if current is None:
        return head  # 位置超出范围
    # 插入节点
    new_node = Node(val)
    new_node.next = current.next  # 新节点后继指向current的后继
    new_node.prev = current  # 新节点前驱指向current
    if current.next:
        current.next.prev = new_node  # current后继的前驱指向新节点
    current.next = new_node  # current的后继指向新节点
    return head


def create_doubly_linked_list(arr):
    if not arr:
        return None
    head = Node(arr[0])
    current = head
    for val in arr[1:]:
        new_node = Node(val)
        current.next = new_node
        new_node.prev = current
        current = new_node
    return head


def traverse(head):
    result = []
    current = head
    while current:
        result.append(current.val)
        current = current.next
    return result


# 测试
if __name__ == "__main__":
    head = create_doubly_linked_list([1, 3, 4])
    new_head = insert_at_position(head, 2, 2)
    print(traverse(new_head))  # 输出: [1, 2, 3, 4]

    head2 = create_doubly_linked_list([1, 2])
    new_head2 = insert_at_position(head2, 3, 3)  # 插入末尾
    print(traverse(new_head2))  # 输出: [1, 2, 3]